import java.util.*;

public class t1711 {
    //1711. 大餐计数 中等
    public static void main(String[] args) {
       int arr[] = new int [100000];
        Arrays.fill(arr,32);
//        int n = 1;
//        for(int i = 1;i<=9;i++){
//            n*=10;
//        }
//        n+=7;
        //计算100000*99999/2-->50000*99999
//        System.out.println(n);
//        int a = 5;
//        int b = 5*99999;
//        long num = 50000L*99999L;
//        System.out.println(num%n);
        //int deliciousness[] = {2,14,11,5,1744,2352,0,1,1300,2796,0,4,376,1672,73,55,2006,42,10,6,0,2,2,0,0,1,0,1,0,2,271,241,1,63,1117,931,3,5,378,646,2,0,2,0,15,1};
        long sr = System.currentTimeMillis();
//        arr = new int[]{1,1,3,1,3,3,7};
        System.out.println(countPairs(arr));
        long ed = System.currentTimeMillis();
        System.out.println(ed - sr);
        System.out.println("*****************");
        //System.out.println(2<<1);
    }
    public static int countPairs1(int[] deliciousness) {
        final int MOD = 1000000007;
        int maxVal = 0;
        for (int val : deliciousness) {
            maxVal = Math.max(maxVal, val);
        }
        int maxSum = maxVal * 2;
        int pairs = 0;
        Map<Integer, Integer> map = new HashMap<Integer, Integer>();
        int n = deliciousness.length;
        for (int i = 0; i < n; i++) {
            int val = deliciousness[i];
            for (int sum = 1; sum <= maxSum; sum <<= 1) {
                int count = map.getOrDefault(sum - val, 0);
                pairs = (pairs + count) % MOD;
            }
            map.put(val, map.getOrDefault(val, 0) + 1);
        }
        return pairs;
    }


    //超时
    public static int countPairs(int[] deliciousness) {
        int n = 1000000007;
        long count = 0L;
        int len = deliciousness.length;

        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < len; i++) {
            Integer k = map.get(deliciousness[i]);
            map.put(deliciousness[i], k == null ? 1 : k + 1);
        }

        Set<Integer> set = map.keySet();
        Integer[] arr = set.toArray(new Integer[set.size()]);
        Arrays.sort(arr);
        int maxVal = arr[arr.length-1]*2;
        len = arr.length;
        for (int i = 0; i < len; i++) {
            for (int k = 1; k <= maxVal; k <<= 1) {
                if(k-arr[i]>0&&k-arr[i]==arr[i]){
                    count+=map.get(k-arr[i])==null?0:
                            (((long)map.get(k-arr[i])%2==0?(long)map.get(k-arr[i])/2:(long)map.get(k-arr[i]))
                                    *
                                    ((long)(map.get(k-arr[i])-1)%2==0?(long)(map.get(k-arr[i])-1)/2:(long)map.get(k-arr[i])-1));
                }else if(k-arr[i]>0){
                    count+=map.get(k-arr[i])==null?0:(map.get(arr[i])*(map.get(k-arr[i])));
                }
                count%=n;

            }
            map.replace(arr[i],0);
            //超时 优化后碾压官解
//            for (int j = i; j < len; j++) {
//                int k = arr[i] + arr[j];
//                if (k>0&&(k & k - 1) == 0) {
//                   // System.out.println(arr[i]+"////"+arr[j]);
//               //    System.out.println(map.get(arr[i]) + "--" + map.get(arr[j]));
//                    if (j == i&&map.get(arr[i])>1) {
////                        System.out.println("6666");
//                        if(map.get(arr[j])%2==0){
//                            count += ((long)map.get(arr[j])/2*(long)(map.get(arr[j])-1));
//                        }else{
//                            count += (map.get(arr[j])*(map.get(arr[j])-1)/2);
//                        }
//
//                    } else if(j!=i){
//                        count += map.get(arr[i]) * map.get(arr[j]);
//                    }
//                    count%=n;
//                   // System.out.println(count%n);
//                }
//            }
        }
        return (int)count;
    }
}
